package com.sunny.l12;

import java.util.*;

public class Solution {

    Map<String, Boolean> map = new HashMap<>();

//    public static void main(String[] args) {
//
//        String s = "leetcode";
//        Set<String> dict = new HashSet<>(Arrays.asList("leet", "code"));
//        Solution solution = new Solution();
//        System.out.println(solution.wordBreak(s, dict));
//
//    }

    public boolean wordBreak(String s, Set<String> dict) {

        return dfs(s, dict);

    }

    public boolean dfs(String s, Set<String> dict){
        if(map.containsKey(s)){
            return map.get(s);
        }
        int len = s.length();
        boolean res = false;
        if("".equals(s)){
            return true;
        }else {
            for (int i = 0; i < len && !res; i++) {
                String tmp = s.substring(0, i + 1);
                if (dict.contains(tmp)) {
                    res = dfs(s.substring(i + 1, len), dict);
                }
            }
        }
        map.put(s, res);
        return res;
    }

}
